package algorithm

/*
	二维数组寻找通路(0: 通路, 1: 障碍物)
*/

// 深度优先搜索(DFS)
func IsPathExistsDFS(list [][]int, startX, startY, targetX, targetY int) bool {
	if startX < 0 || startY < 0 || startX >= len(list) || startY >= len(list[0]) {
		return false
	}
	if list[startX][startY] == 1 {
		return false
	}
	if startX == targetX && startY == targetY {
		return true
	}
	list[startX][startY] = 1
	if IsPathExistsDFS(list, startX-1, startY, targetX, targetY) {
		return true
	}
	if IsPathExistsDFS(list, startX+1, startY, targetX, targetY) {
		return true
	}
	if IsPathExistsDFS(list, startX, startY-1, targetX, targetY) {
		return true
	}
	if IsPathExistsDFS(list, startX, startY+1, targetX, targetY) {
		return true
	}
	return false
}

// 广度优先搜索(BFS)
func IsPathExistsBFS(list [][]int, startX, startY, targetX, targetY int) bool {
	if startX < 0 || startY < 0 || startX >= len(list) || startY >= len(list[0]) {
		return false
	}
	if list[startX][startY] == 1 {
		return false
	}
	if startX == targetX && startY == targetY {
		return true
	}
	queue := [][]int{{startX, startY}}
	for len(queue) > 0 {
		x, y := queue[0][0], queue[0][1]
		queue = queue[1:]
		list[x][y] = 1
		if x-1 >= 0 && list[x-1][y] == 0 {
			if x-1 == targetX && y == targetY {
				return true
			}
			queue = append(queue, []int{x - 1, y})
		}
		if x+1 < len(list) && list[x+1][y] == 0 {
			if x+1 == targetX && y == targetY {
				return true
			}
			queue = append(queue, []int{x + 1, y})
		}
		if y-1 >= 0 && list[x][y-1] == 0 {
			if x == targetX && y-1 == targetY {
				return true
			}
			queue = append(queue, []int{x, y - 1})
		}
		if y+1 < len(list[0]) && list[x][y+1] == 0 {
			if x == targetX && y+1 == targetY {
				return true
			}
			queue = append(queue, []int{x, y + 1})
		}
	}
	return false
}
